package sort.leetcode;

/**
 * 数组中的第K个最大元素
 * https://leetcode-cn.com/problems/kth-largest-element-in-an-array/
 * @author yuisama
 * @date 2021/12/23 13:53
 **/
public class Num215 {
    // 快排分区思想解决数组中第k大元素查找，时间复杂度为O(n)
    public int findKthLargest(int[] nums, int k) {
        return findKthLargestInternal(nums,0,nums.length - 1,nums.length - k);
    }

    /**
     * 在nums[l..r]上找第k大元素
     * @param nums
     * @param l
     * @param r
     * @param k
     * @return
     */
    private int findKthLargestInternal(int[] nums, int l, int r, int k) {
        if (l > r) {
            return -1;
        }
        int index = partition(l,r,nums);
        // 此时找到了
        if (index == k) return nums[index];
        else if (k > index) {
            // 在右区间找
            return findKthLargestInternal(nums,index + 1,r,k);
        }
        // 在左区间找
        return findKthLargestInternal(nums,l,index - 1,k);
    }

    /**
     * 随机化分区
     * @param nums
     * @return
     */
    private int partition(int l,int r,int[] nums) {
        int randomIndex = (int) (Math.random() * (r - l + 1)) + l;
        swap(nums,l,randomIndex);
        int v = nums[l];
        int j = l;
        // nums[l + 1...j] <= v ; nums[j + 1...i) > v
        for (int i = l + 1; i <= r; i++) {
            if (nums[i] <= v) {
                swap(nums,i,j + 1);
                j ++;
            }
        }
        swap(nums,l,j);
        return j;
    }

    private void swap(int[] nums, int i, int i1) {
        int temp = nums[i];
        nums[i] = nums[i1];
        nums[i1] = temp;
    }
}